home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer)…68k, x86, SPARC, PA-RISC] / NeXTSTEP 3.3 Dev Intel.iso / NextDeveloper / Source / GNU / debug / Common / objc / maptable.h
Text File  |  1991-12-10  |  4KB  |  106 lines
  1. /*    maptable.h
  2.     Scalable hash table of mappings.
  3.     Bertrand, August 1990
  4.     Copyright 1990 NeXT, Inc.
  5. */
  6.  
  7. #ifndef _OBJC_MAPTABLE_H_
  8. #define _OBJC_MAPTABLE_H_
  9.  
  10. #import <objc/objc.h>
  11. #import <objc/zone.h>
  12.  
  13. /***************    Definitions        ***************/
  14.  
  15.     /* This module allows hashing of arbitrary associations [key -> value].  Keys and values must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
  16.     NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1.
  17.     As well-behaved scalable data structures, hash tables double in size when they start becoming full, thus guaranteeing both average constant time access and linear size. */
  18.  
  19. typedef struct _NXMapTable {
  20.     /* private data structure; may change */
  21.     const struct _NXMapTablePrototype    *prototype;
  22.     unsigned    count;
  23.     unsigned    nbBuckets;
  24.     void    *buckets;
  25. } NXMapTable;
  26.  
  27. typedef struct _NXMapTablePrototype {
  28.     unsigned    (*hash)(NXMapTable *, const void *key);
  29.     int        (*isEqual)(NXMapTable *, const void *key1, const void *key2);
  30.     void    (*free)(NXMapTable *, void *key, void *value);
  31.     int        style; /* reserved for future expansion; currently 0 */
  32. } NXMapTablePrototype;
  33.     
  34.     /* invariants assumed by the implementation: 
  35.     A - key != -1
  36.     B - key1 == key2 => hash(key1) == hash(key2)
  37.         when key varies over time, hash(key) must remain invariant
  38.         e.g. if string key, the string must not be changed
  39.     C - isEqual(key1, key2) => key1 == key2
  40.     */
  41.  
  42. #define NX_MAPNOTAKEY    ((void *)(-1))
  43.  
  44. /***************    Functions        ***************/
  45.  
  46. extern NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, NXZone *zone);
  47. extern NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity);
  48.     /* capacity is only a hint; 0 creates a small table */
  49.  
  50. extern void NXFreeMapTable(NXMapTable *table);
  51.     /* call free for each pair, and recovers table */
  52.     
  53. extern void NXResetMapTable(NXMapTable *table);
  54.     /* free each pair; keep current capacity */
  55.  
  56. extern BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2);
  57.     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
  58.  
  59. extern unsigned NXCountMapTable(NXMapTable *table);
  60.     /* current number of data in table */
  61.     
  62. extern void *NXMapMember(NXMapTable *table, const void *key, void **value);
  63.     /* return original table key or NX_MAPNOTAKEY.  If key is found, value is set */
  64.     
  65. extern void *NXMapGet(NXMapTable *table, const void *key);
  66.     /* return original corresponding value or NULL.  When NULL need be stored as value, NXMapMember can be used to test for presence */
  67.     
  68. extern void *NXMapInsert(NXMapTable *table, const void *key, const void *value);
  69.     /* override preexisting pair; Return previous value or NULL. */
  70.     
  71. extern void *NXMapRemove(NXMapTable *table, const void *key);
  72.     /* previous value or NULL is returned */
  73.     
  74. /* Iteration over all elements of a table consists in setting up an iteration state and then to progress until all entries have been visited.  An example of use for counting elements in a table is:
  75.     unsigned    count = 0;
  76.     const MyKey    *key;
  77.     const MyValue    *value;
  78.     NXMapState    state = NXInitMapState(table);
  79.     while(NXNextMapState(table, &state, &key, &value)) {
  80.     count++;
  81.     }
  82. */
  83.  
  84. typedef struct {int index;} NXMapState;
  85.     /* callers should not rely on actual contents of the struct */
  86.  
  87. extern NXMapState NXInitMapState(NXMapTable *table);
  88.  
  89. extern int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value);
  90.     /* returns 0 when all elements have been visited */
  91.  
  92. /***************    Conveniences        ***************/
  93.  
  94. extern const NXMapTablePrototype NXPtrValueMapPrototype;
  95.     /* hashing is pointer/integer hashing;
  96.       isEqual is identity;
  97.       free is no-op. */
  98. extern const NXMapTablePrototype NXStrValueMapPrototype;
  99.     /* hashing is string hashing;
  100.       isEqual is strcmp;
  101.       free is no-op. */
  102. extern const NXMapTablePrototype NXObjectMapPrototype;
  103.     /* for objects; uses methods: hash, isEqual:, free, all for key. */
  104.  
  105. #endif /* _OBJC_MAPTABLE_H_ */
  106.